import java.util.*;

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        ListNode newHead1 = reseverList(head1);
        ListNode newHead2 = reseverList(head2);
        ListNode retTmp = cal(newHead1, newHead2);
        ListNode ret = reseverList(retTmp);
        return ret;
    }

    private ListNode reseverList(ListNode head) {
        ListNode curN = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode node = new ListNode(cur.val);
            node.next = curN;
            curN = node;
            cur = cur.next;
        }
        return curN;
    }

    private ListNode cal(ListNode head1, ListNode head2) {
        int m = 0;//进位
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        ListNode newHead = new ListNode(0);
        ListNode cur = newHead;//带头节点
        while (cur1 != null && cur2 != null) {
            int sum = cur1.val + cur2.val + m;
            if (sum < 10) {
                ListNode node = new ListNode(sum);
                cur.next = node;
                cur = cur.next;
                m = 0;
            } else {
                ListNode node = new ListNode(sum % 10);
                cur.next = node;
                cur = cur.next;
                m = 1;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        while (cur1 != null) {
            int sum = cur1.val + m;
            if (sum < 10) {
                ListNode node = new ListNode(sum);
                cur.next = node;
                cur = cur.next;
                m = 0;
            } else {
                ListNode node = new ListNode(sum % 10);
                cur.next = node;
                cur = cur.next;
                m = 1;
            }
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            int sum = cur2.val + m;
            if (sum < 10) {
                ListNode node = new ListNode(sum);
                cur.next = node;
                cur = cur.next;
                m = 0;
            } else {
                ListNode node = new ListNode(sum % 10);
                cur.next = node;
                cur = cur.next;
                m = 1;
            }
            cur2 = cur2.next;
        }
        if(m == 1) {
            ListNode node = new ListNode(1);
            cur.next = node;
            cur = cur.next;
            m = 0;
        }
        return newHead.next;
    }
}